#define _CRT_SECURE_NO_WARNINGS

//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int n, k;
//int q[N];
//
//int quick_sort(int* a, int l, int r, int k)
//{
//	if (l >= r) return a[l];
//
//	int x = a[l], i = l - 1, j = r + 1;
//	while (i < j)
//	{
//		do i++; while (a[i] < x);
//		do j--; while (a[j] > x);
//		if (i < j) swap(a[i], a[j]);
//	}
//
//	int sl = j - l + 1;
//	if (sl >= k) return quick_sort(a, l, j, k);
//	else return quick_sort(a, j + 1, r, k - sl);
//}
//
//int main()
//{
//	cin >> n >> k;
//	for (int i = 0; i < n; i++) cin >> q[i];
//
//	cout << quick_sort(q, 0, n - 1, k) << endl;
//
//	return 0;
//}


//#include <iostream>
//
//using namespace std;
//
//typedef long long LL;
//const int N = 100010;
//int n;
//int q[N], tmp[N];
//
//LL merge_sort(int l, int r)
//{
//	if (l >= r) return 0;
//
//	int mid = (l + r) >> 1;
//
//	LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
//
//	int k = 0, i = l, j = mid + 1;
//	while (i <= mid && j <= r)
//	{
//		if (q[i] <= q[j]) tmp[k++] = q[i++];
//		else
//		{
//			tmp[k++] = q[j++];
//			res += mid - i + 1;
//		}
//	}
//
//	while (i <= mid) tmp[k++] = q[i++];
//	while (j <= r) tmp[k++] = q[j++];
//
//	for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
//
//	return res;
//}
//
//int main()
//{
//	cin >> n;
//	for (int i = 0; i < n; i++) cin >> q[i];
//
//	cout << merge_sort(0, n - 1) << endl;
//
//	return 0;
//}


//#include <iostream>
//#include <unordered_map>
//using namespace std;
//
//const int N = 100010;
//int n, m, x;
//int a[N], b[N];
//
//int main()
//{
//	unordered_map<int, int> mp;
//	cin >> n >> m >> x;
//	for (int i = 0; i < n; i++) cin >> a[i], mp[a[i]] = i;
//	for (int i = 0; i < m; i++) cin >> b[i];
//
//	for (int i = 0; i < m; i++)
//	{
//		int find = x - b[i];
//		if (mp.count(find))
//		{
//			cout << mp[find] << ' ' << i << endl;
//			break;
//		}
//	}
//
//	return 0;
//}



